# 二叉树的基础功能
# 
# 
from collections import deque
# 二叉树的定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right 


# 通用数组转二叉树
def array_to_binary_tree(arr):
    if not arr:
        return None
    
    root = TreeNode(arr[0])
    queue = [root]
    i = 1

    # while queue and i < len(arr):
    #     node = queue.pop(0)
    #     # 左子节点
    #     if i < len(arr):
    #         node.left = TreeNode(arr[i])
    #         queue.append(node.left)
    #         i += 1
    #     # 右子节点
    #     if i < len(arr):
    #         node.right = TreeNode(arr[i])
    #         queue.append(node.right)
    #         i += 1
    # 修复版本，如果列表中存在None时，层序遍历构建二叉树
    while queue and i < len(arr):
        node = queue.pop(0)

        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
            
        i += 1
        
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1

        
    return root


# 二叉树层序遍历构建出数组
def level_order_basic(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.val)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result



if __name__ == "__main__":


    arr = [4,2,7,1,3,6,9]
    print(arr)
    root = array_to_binary_tree(arr=arr)
    a1 = level_order_basic(root)
    
    print(a1)
    

